home *** CD-ROM | disk | FTP | other *** search
/ InterCD 2000 September / september_2000.iso / intercd / root / ^Linux / WindowMaker / WINGs / bagtree.c < prev    next >
Encoding:
C/C++ Source or Header  |  2000-04-02  |  16.7 KB  |  921 lines
  1.  
  2.  
  3.  
  4.  
  5. #include <stdlib.h>
  6. #include <string.h>
  7.  
  8. #include "WUtil.h"
  9.  
  10.  
  11. typedef struct W_Node {
  12.     struct W_Node *parent;
  13.     struct W_Node *left;
  14.     struct W_Node *right;
  15.     int color;
  16.     
  17.     void *data;
  18.     int index;
  19. } W_Node;
  20.  
  21.  
  22. typedef struct W_TreeBag {
  23.     W_Node *root;
  24.     
  25.     W_Node *nil;               /* sentinel */
  26.     
  27.     int count;
  28. } W_TreeBag;
  29.  
  30.  
  31.  
  32. static int getItemCount(WMBag *self);
  33. static int appendBag(WMBag *self, WMBag *bag);
  34. static int putInBag(WMBag *self, void *item);
  35. static int insertInBag(WMBag *self, int index, void *item);
  36. static int removeFromBag(WMBag *bag, void *item);
  37. static int eraseFromBag(WMBag *bag, int index);
  38. static int deleteFromBag(WMBag *bag, int index);
  39. static void *getFromBag(WMBag *bag, int index);
  40. static int countInBag(WMBag *bag, void *item);
  41. static int firstInBag(WMBag *bag, void *item);
  42. static void *replaceInBag(WMBag *bag, int index, void *item);
  43. static int sortBag(WMBag *bag, int (*comparer)(const void*, const void*));
  44. static void emptyBag(WMBag *bag);
  45. static void freeBag(WMBag *bag);
  46. static void mapBag(WMBag *bag, void (*function)(void*, void*), void *data);
  47. static int findInBag(WMBag *bag, int (*match)(void*,void*), void *data);
  48. static void *first(WMBag *bag, WMBagIterator *ptr);
  49. static void *last(WMBag *bag, WMBagIterator *ptr);
  50. static void *next(WMBag *bag, WMBagIterator *ptr);
  51. static void *previous(WMBag *bag, WMBagIterator *ptr);
  52. static void *iteratorAtIndex(WMBag *bag, int index, WMBagIterator *ptr);
  53. static int indexForIterator(WMBag *bag, WMBagIterator ptr);
  54.  
  55.  
  56. static W_BagFunctions bagFunctions = {
  57.     getItemCount,
  58.     appendBag,
  59.     putInBag,
  60.     insertInBag,
  61.     removeFromBag,
  62.     eraseFromBag,
  63.     deleteFromBag,
  64.     getFromBag,
  65.     firstInBag,
  66.     countInBag,
  67.     replaceInBag,
  68.     sortBag,
  69.     emptyBag,
  70.     freeBag,
  71.     mapBag,
  72.     findInBag,
  73.     first,
  74.     last,
  75.     next,
  76.     previous,
  77.     iteratorAtIndex,
  78.     indexForIterator
  79. };
  80.  
  81.  
  82.  
  83.  
  84. #define IS_LEFT(node) (node == node->parent->left)
  85. #define IS_RIGHT(node) (node == node->parent->right)
  86.  
  87.  
  88.  
  89. static void leftRotate(W_TreeBag *tree, W_Node *node)
  90. {
  91.     W_Node *node2;
  92.     
  93.     node2 = node->right;
  94.     node->right = node2->left;
  95.  
  96.     node2->left->parent = node;
  97.  
  98.     node2->parent = node->parent;
  99.  
  100.     if (node->parent == tree->nil) {
  101.     tree->root = node2;
  102.     } else {
  103.     if (IS_LEFT(node)) {
  104.         node->parent->left = node2;
  105.     } else {
  106.         node->parent->right = node2;
  107.     }
  108.     }
  109.     node2->left = node;
  110.     node->parent = node2;
  111. }
  112.  
  113.  
  114.  
  115. static void rightRotate(W_TreeBag *tree, W_Node *node)
  116. {
  117.     W_Node *node2;
  118.     
  119.     node2 = node->left;
  120.     node->left = node2->right;
  121.     
  122.     node2->right->parent = node;
  123.     
  124.     node2->parent = node->parent;
  125.  
  126.     if (node->parent == tree->nil) {
  127.     tree->root = node2;
  128.     } else {
  129.     if (IS_LEFT(node)) {
  130.         node->parent->left = node2;
  131.     } else {
  132.         node->parent->right = node2;
  133.     }
  134.     }
  135.     node2->right = node;
  136.     node->parent = node2;
  137. }
  138.  
  139.  
  140.  
  141. static void treeInsert(W_TreeBag *tree, W_Node *node)
  142. {
  143.     W_Node *y = tree->nil;
  144.     W_Node *x = tree->root;
  145.     
  146.     while (x != tree->nil) {
  147.     y = x;
  148.     if (node->index <= x->index)
  149.         x = x->left;
  150.     else
  151.         x = x->right;
  152.     }
  153.     node->parent = y;
  154.     if (y == tree->nil)
  155.     tree->root = node;
  156.     else if (node->index <= y->index)
  157.     y->left = node;
  158.     else
  159.     y->right = node;
  160. }
  161.  
  162.  
  163. static void rbTreeInsert(W_TreeBag *tree, W_Node *node)
  164. {
  165.     W_Node *y;
  166.     
  167.     treeInsert(tree, node);
  168.  
  169.     node->color = 'R';
  170.     
  171.     while (node != tree->root && node->parent->color == 'R') {
  172.     if (IS_LEFT(node->parent)) {
  173.         y = node->parent->parent->right;
  174.         
  175.         if (y->color == 'R') {
  176.         
  177.         node->parent->color = 'B';
  178.         y->color = 'B';
  179.         node->parent->parent->color = 'R';
  180.         node = node->parent->parent;
  181.         
  182.         } else {
  183.         if (IS_RIGHT(node)) {
  184.             node = node->parent;
  185.             leftRotate(tree, node);
  186.         }
  187.         node->parent->color = 'B';
  188.         node->parent->parent->color = 'R';
  189.         rightRotate(tree, node->parent->parent);
  190.         }
  191.     } else {
  192.         y = node->parent->parent->left;
  193.         
  194.         if (y->color == 'R') {
  195.         
  196.         node->parent->color = 'B';
  197.         y->color = 'B';
  198.         node->parent->parent->color = 'R';
  199.         node = node->parent->parent;
  200.         
  201.         } else {
  202.         if (IS_LEFT(node)) {
  203.             node = node->parent;
  204.             rightRotate(tree, node);
  205.         }
  206.         node->parent->color = 'B';
  207.         node->parent->parent->color = 'R';
  208.         leftRotate(tree, node->parent->parent);
  209.         }
  210.     }
  211.     }
  212.     tree->root->color = 'B';
  213. }
  214.  
  215.  
  216.  
  217. static void rbDeleteFixup(W_TreeBag *tree, W_Node *node)
  218. {
  219.     W_Node *w;
  220.     
  221.     while (node != tree->root && node->color == 'B') {
  222.     if (IS_LEFT(node)) {
  223.         w = node->parent->right;
  224.         if (w->color == 'R') {
  225.         w->color = 'B';
  226.         node->parent->color = 'R';
  227.         leftRotate(tree, node->parent);
  228.         w = node->parent->right;
  229.         }
  230.         if (w->left->color == 'B' && w->right->color == 'B') {
  231.         w->color = 'R';
  232.         node = node->parent;
  233.         } else {
  234.         if (w->right->color == 'B') {
  235.             w->left->color = 'B';
  236.             w->color = 'R';
  237.             rightRotate(tree, w);
  238.             w = node->parent->right;
  239.         }
  240.         w->color = node->parent->color;
  241.         node->parent->color = 'B';
  242.         w->right->color = 'B';
  243.         leftRotate(tree, node->parent);
  244.         node = tree->root;
  245.         }
  246.     } else {
  247.         w = node->parent->left;
  248.         if (w->color == 'R') {
  249.         w->color = 'B';
  250.         node->parent->color = 'R';
  251.         leftRotate(tree, node->parent);
  252.         w = node->parent->left;
  253.         }
  254.         if (w->left->color == 'B' && w->right->color == 'B') {
  255.         w->color = 'R';
  256.         node = node->parent;
  257.         } else {
  258.         if (w->left->color == 'B') {
  259.             w->right->color = 'B';
  260.             w->color = 'R';
  261.             rightRotate(tree, w);
  262.             w = node->parent->left;
  263.         }
  264.         w->color = node->parent->color;
  265.         node->parent->color = 'B';
  266.         w->left->color = 'B';
  267.         leftRotate(tree, node->parent);
  268.         node = tree->root;
  269.         }        
  270.     }
  271.     }
  272.     node->color = 'B';
  273. }
  274.  
  275.  
  276. static W_Node *treeMinimum(W_Node *node, W_Node *nil)
  277. {
  278.     while (node->left != nil)
  279.     node = node->left;
  280.     return node;
  281. }
  282.  
  283.  
  284. static W_Node *treeMaximum(W_Node *node, W_Node *nil)
  285. {
  286.     while (node->right != nil)
  287.     node = node->right;
  288.     return node;
  289. }
  290.  
  291.  
  292. static W_Node *treeSuccessor(W_Node *node, W_Node *nil)
  293. {
  294.     W_Node *y;
  295.     
  296.     if (node->right != nil) {
  297.     return treeMinimum(node->right, nil);
  298.     }
  299.     y = node->parent;
  300.     while (y != nil && node == y->right) {
  301.     node = y;
  302.     y = y->parent;
  303.     }
  304.     return y;
  305. }
  306.  
  307.  
  308. static W_Node *treePredecessor(W_Node *node, W_Node *nil)
  309. {
  310.     W_Node *y;
  311.     
  312.     if (node->left != nil) {
  313.     return treeMaximum(node->left, nil);
  314.     }
  315.     y = node->parent;
  316.     while (y != nil && node == y->left) {
  317.     node = y;
  318.     y = y->parent;
  319.     }
  320.     return y;
  321. }
  322.  
  323.  
  324. static W_Node *rbTreeDelete(W_TreeBag *tree, W_Node *node)
  325. {
  326.     W_Node *nil = tree->nil;
  327.     W_Node *x, *y;
  328.     
  329.     if (node->left == nil || node->right == nil) {
  330.     y = node;
  331.     } else {
  332.     y = treeSuccessor(node, nil);
  333.     }
  334.     
  335.     if (y->left != nil) {
  336.     x = y->left;
  337.     } else {
  338.     x = y->right;
  339.     }
  340.     
  341.     x->parent = y->parent;
  342.     
  343.     if (y->parent == nil) {
  344.     tree->root = x;
  345.     } else {
  346.     if (IS_LEFT(y)) {
  347.         y->parent->left = x;
  348.     } else {
  349.         y->parent->right = x;
  350.     }
  351.     }
  352.     if (y != node) {
  353.     node->index = y->index;
  354.     node->data = y->data;
  355.     }
  356.     if (y->color == 'B') {
  357.     rbDeleteFixup(tree, x);
  358.     }
  359.     
  360.     return y;
  361. }
  362.  
  363.  
  364.  
  365. static W_Node *treeSearch(W_Node *root, W_Node *nil, int index)
  366. {
  367.     if (root == nil || root->index == index) {
  368.     return root;
  369.     }
  370.     
  371.     if (index < root->index) {
  372.     return treeSearch(root->left, nil, index);
  373.     } else {
  374.     return treeSearch(root->right, nil, index);
  375.     }
  376. }
  377.  
  378.  
  379. static W_Node *treeFind(W_Node *root, W_Node *nil, void *data)
  380. {
  381.     W_Node *tmp;
  382.     
  383.     if (root == nil || root->data == data)
  384.     return root;
  385.  
  386.     tmp = treeFind(root->left, nil, data);
  387.     if (tmp != nil)
  388.     return tmp;
  389.     
  390.     tmp = treeFind(root->right, nil, data);
  391.  
  392.     return tmp;
  393. }
  394.  
  395.  
  396.  
  397.  
  398.  
  399. #if 0
  400. static char buf[512];
  401.  
  402. static void printNodes(W_Node *node, W_Node *nil, int depth)
  403. {
  404.     if (node == nil) {
  405.     return;
  406.     }
  407.     
  408.     printNodes(node->left, nil, depth+1);
  409.  
  410.     memset(buf, ' ', depth*2);
  411.     buf[depth*2] = 0;
  412.     if (IS_LEFT(node))
  413.     printf("%s/(%2i\n", buf, node->index);
  414.     else
  415.     printf("%s\\(%2i\n", buf, node->index);
  416.  
  417.     printNodes(node->right, nil, depth+1);
  418. }
  419.  
  420.  
  421. void PrintTree(WMBag *bag)
  422. {
  423.     W_TreeBag *tree = (W_TreeBag*)bag->data;
  424.     
  425.     printNodes(tree->root, tree->nil, 0);
  426. }
  427. #endif
  428.  
  429.  
  430.  
  431.  
  432. #define SELF ((W_TreeBag*)self->data)
  433.  
  434. WMBag *WMCreateTreeBag(void)
  435. {
  436.     return WMCreateTreeBagWithDestructor(NULL);
  437. }
  438.  
  439.  
  440. WMBag *WMCreateTreeBagWithDestructor(void (*destructor)(void*))
  441. {
  442.     WMBag *bag;
  443.     W_TreeBag *tree;
  444.     
  445.     bag = wmalloc(sizeof(WMBag));
  446.  
  447.     bag->data = tree = wmalloc(sizeof(W_TreeBag));
  448.     memset(tree, 0, sizeof(W_TreeBag));
  449.  
  450.     tree->nil = wmalloc(sizeof(W_Node));
  451.     memset(tree->nil, 0, sizeof(W_Node));
  452.     tree->nil->left = tree->nil->right = tree->nil->parent = tree->nil;
  453.     tree->nil->index = WBNotFound;
  454.  
  455.     tree->root = tree->nil;
  456.     
  457.     bag->destructor = destructor;
  458.     
  459.     bag->func = bagFunctions;
  460.     
  461.     return bag;
  462. }
  463.  
  464.  
  465. static int getItemCount(WMBag *self)
  466. {
  467.     return SELF->count;
  468. }
  469.  
  470.  
  471. static int appendBag(WMBag *self, WMBag *bag)
  472. {
  473.     WMBagIterator ptr;
  474.     void *data;
  475.     
  476.     for (data = first(bag, &ptr); data != NULL; data = next(bag, &ptr)) {
  477.     if (!putInBag(self, data))
  478.         return 0;
  479.     }
  480.     
  481.     return 1;
  482. }
  483.  
  484.  
  485. static int putInBag(WMBag *self, void *item)
  486. {
  487.     W_Node *ptr;
  488.     
  489.     ptr = wmalloc(sizeof(W_Node));
  490.     
  491.     ptr->data = item;
  492.     ptr->index = SELF->count;
  493.     ptr->left = SELF->nil;
  494.     ptr->right = SELF->nil;
  495.     ptr->parent = SELF->nil;
  496.     
  497.     rbTreeInsert(SELF, ptr);
  498.     
  499.     SELF->count++;
  500.     
  501.     return 1;
  502. }
  503.  
  504.  
  505. static int insertInBag(WMBag *self, int index, void *item)
  506. {
  507.     W_Node *ptr;
  508.  
  509.     ptr = wmalloc(sizeof(W_Node));
  510.  
  511.     ptr->data = item;
  512.     ptr->index = index;
  513.     ptr->left = SELF->nil;
  514.     ptr->right = SELF->nil;
  515.     ptr->parent = SELF->nil;
  516.  
  517.     rbTreeInsert(SELF, ptr);
  518.     
  519.     while ((ptr = treeSuccessor(ptr, SELF->nil)) != SELF->nil) {
  520.     ptr->index++;
  521.     }
  522.     
  523.     
  524.     SELF->count++;
  525.  
  526.     return 1;
  527. }
  528.  
  529.  
  530.  
  531. static int removeFromBag(WMBag *self, void *item)
  532. {
  533.     W_Node *ptr = treeFind(SELF->root, SELF->nil, item);
  534.     
  535.     if (ptr != SELF->nil) {
  536.     W_Node *tmp;
  537.     
  538.     SELF->count--;
  539.     
  540.     tmp = treeSuccessor(ptr, SELF->nil);
  541.     while (tmp != SELF->nil) {
  542.         tmp->index--;
  543.         tmp = treeSuccessor(tmp, SELF->nil);
  544.     }
  545.     
  546.     ptr = rbTreeDelete(SELF, ptr);
  547.     if (self->destructor)
  548.         self->destructor(ptr->data);
  549.     free(ptr);
  550.  
  551.     return 1;
  552.     } else {
  553.     return 0;
  554.     }
  555. }
  556.  
  557.  
  558.  
  559. static int eraseFromBag(WMBag *self, int index)
  560. {
  561.     W_Node *ptr = treeSearch(SELF->root, SELF->nil, index);
  562.     
  563.     if (ptr != SELF->nil) {
  564.     
  565.     SELF->count--;
  566.     
  567.     ptr = rbTreeDelete(SELF, ptr);
  568.     if (self->destructor)
  569.         self->destructor(ptr->data);
  570.     free(ptr);
  571.  
  572.     return 1;
  573.     } else {
  574.     return 0;
  575.     }
  576. }
  577.  
  578.  
  579. static int deleteFromBag(WMBag *self, int index)
  580. {
  581.     W_Node *ptr = treeSearch(SELF->root, SELF->nil, index);
  582.     
  583.     if (ptr != SELF->nil) {
  584.     W_Node *tmp;
  585.     
  586.     SELF->count--;
  587.     
  588.     tmp = treeSuccessor(ptr, SELF->nil);
  589.     while (tmp != SELF->nil) {
  590.         tmp->index--;
  591.         tmp = treeSuccessor(tmp, SELF->nil);
  592.     }
  593.     
  594.     ptr = rbTreeDelete(SELF, ptr);
  595.     if (self->destructor)
  596.         self->destructor(ptr->data);
  597.     free(ptr);
  598.  
  599.     return 1;
  600.     } else {
  601.     return 0;
  602.     }
  603. }
  604.  
  605.  
  606. static void *getFromBag(WMBag *self, int index)
  607. {    
  608.     W_Node *node;
  609.  
  610.     node = treeSearch(SELF->root, SELF->nil, index);
  611.     if (node != SELF->nil)
  612.     return node->data;
  613.     else
  614.     return NULL;
  615. }
  616.  
  617.  
  618.  
  619. static int firstInBag(WMBag *self, void *item)
  620. {
  621.     W_Node *node;
  622.     
  623.     node = treeFind(SELF->root, SELF->nil, item);
  624.     if (node != SELF->nil)
  625.     return node->index;
  626.     else
  627.     return WBNotFound;
  628. }
  629.  
  630.  
  631.  
  632. static int treeCount(W_Node *root, W_Node *nil, void *item)
  633. {
  634.     int count = 0;
  635.     
  636.     if (root == nil)
  637.     return 0;
  638.     
  639.     if (root->data == item)
  640.     count++;
  641.  
  642.     if (root->left != nil)
  643.     count += treeCount(root->left, nil, item);
  644.     
  645.     if (root->right != nil)
  646.     count += treeCount(root->right, nil, item);
  647.  
  648.     return count;
  649. }
  650.  
  651.  
  652.  
  653. static int countInBag(WMBag *self, void *item)
  654. {    
  655.     return treeCount(SELF->root, SELF->nil, item);
  656. }
  657.  
  658.  
  659. static void *replaceInBag(WMBag *self, int index, void *item)
  660. {
  661.     W_Node *ptr = treeSearch(SELF->root, SELF->nil, index);
  662.     void *old = NULL;
  663.  
  664.     if (item == NULL) {
  665.     SELF->count--;
  666.     ptr = rbTreeDelete(SELF, ptr);
  667.     if (self->destructor)
  668.         self->destructor(ptr->data);
  669.     free(ptr);
  670.     } else if (ptr != SELF->nil) {
  671.     old = ptr->data;
  672.     ptr->data = item;
  673.     } else {
  674.     W_Node *ptr;
  675.  
  676.     ptr = wmalloc(sizeof(W_Node));
  677.  
  678.     ptr->data = item;
  679.     ptr->index = index;
  680.     ptr->left = SELF->nil;
  681.     ptr->right = SELF->nil;
  682.     ptr->parent = SELF->nil;
  683.  
  684.     rbTreeInsert(SELF, ptr);
  685.  
  686.     SELF->count++;
  687.     }
  688.     
  689.     return old;
  690. }
  691.  
  692.  
  693.  
  694.  
  695. static int sortBag(WMBag *self, int (*comparer)(const void*, const void*))
  696. {
  697.     void **items;
  698.     W_Node *tmp;
  699.     int i;
  700.  
  701.     if (SELF->count == 0)
  702.     return 1;
  703.  
  704.     items = wmalloc(sizeof(void*)*SELF->count);
  705.     i = 0;
  706.     
  707.     tmp = treeMinimum(SELF->root, SELF->nil);
  708.     while (tmp != SELF->nil) {
  709.     items[i++] = tmp->data;
  710.     tmp = treeSuccessor(tmp, SELF->nil);
  711.     }
  712.  
  713.     qsort(&items[0], SELF->count, sizeof(void*), comparer);
  714.     
  715.     i = 0;
  716.     tmp = treeMinimum(SELF->root, SELF->nil);
  717.     while (tmp != SELF->nil) {
  718.     tmp->index = i;
  719.     tmp->data = items[i++];
  720.     tmp = treeSuccessor(tmp, SELF->nil);
  721.     }
  722.     
  723.     wfree(items);
  724.     
  725.     return 1;
  726. }
  727.  
  728.  
  729.  
  730.  
  731. static void deleteTree(WMBag *self, W_Node *node)
  732. {
  733.     if (node == SELF->nil)
  734.     return;
  735.     
  736.     deleteTree(self, node->left);
  737.     
  738.     if (self->destructor)
  739.     self->destructor(node->data);
  740.     
  741.     deleteTree(self, node->right);
  742.     
  743.     free(node);
  744. }
  745.  
  746.  
  747. static void emptyBag(WMBag *self)
  748. {
  749.     deleteTree(self, SELF->root);
  750.     SELF->root = SELF->nil;
  751.     SELF->count = 0;
  752. }
  753.  
  754.  
  755. static void freeBag(WMBag *self)
  756. {
  757.     emptyBag(self);
  758.     
  759.     free(SELF->nil);
  760.     free(self->data);
  761.     
  762.     free(self);
  763. }
  764.  
  765.  
  766.  
  767. static void mapTree(W_TreeBag *tree, W_Node *node,
  768.             void (*function)(void*, void*), void *data)
  769. {
  770.     if (node == tree->nil)
  771.     return;
  772.     
  773.     mapTree(tree, node->left, function, data);
  774.  
  775.     (*function)(node->data, data);
  776.  
  777.     mapTree(tree, node->right, function, data);
  778. }
  779.  
  780.  
  781. static void mapBag(WMBag *self, void (*function)(void*, void*), void *data)
  782. {
  783.     mapTree(SELF, SELF->root, function, data);
  784. }
  785.  
  786.  
  787.  
  788. static int findInTree(W_TreeBag *tree, W_Node *node, 
  789.               int (*function)(void*,void*), void *cdata)
  790. {
  791.     int index;
  792.     
  793.     if (node == tree->nil)
  794.     return WBNotFound;
  795.     
  796.     index = findInTree(tree, node->left, function, cdata);
  797.     if (index != WBNotFound)
  798.     return index;
  799.  
  800.     if ((*function)(node->data, cdata)) {
  801.     return node->index;
  802.     }
  803.  
  804.     return findInTree(tree, node->right, function, cdata);
  805. }
  806.  
  807.  
  808. static int findInBag(WMBag *self, int (*match)(void*,void*), void *cdata)
  809. {
  810.     return findInTree(SELF, SELF->root, match, cdata);
  811. }
  812.  
  813.  
  814.  
  815.  
  816. static void *first(WMBag *self, WMBagIterator *ptr)
  817. {
  818.     W_Node *node;
  819.     
  820.     node = treeMinimum(SELF->root, SELF->nil);
  821.     
  822.     if (node == SELF->nil) {
  823.     *ptr = NULL;
  824.     
  825.     return NULL;
  826.     } else {
  827.     *ptr = node;
  828.     
  829.     return node->data;
  830.     }
  831. }
  832.  
  833.  
  834.  
  835. static void *last(WMBag *self, WMBagIterator *ptr)
  836. {
  837.  
  838.     W_Node *node;
  839.     
  840.     node = treeMaximum(SELF->root, SELF->nil);
  841.     
  842.     if (node == SELF->nil) {
  843.     *ptr = NULL;
  844.     
  845.     return NULL;
  846.     } else {
  847.     *ptr = node;
  848.     
  849.     return node->data;
  850.     }
  851. }
  852.  
  853.  
  854.  
  855. static void *next(WMBag *self, WMBagIterator *ptr)
  856. {
  857.     W_Node *node;
  858.     
  859.     if (*ptr == NULL)
  860.     return NULL;
  861.     
  862.     node = treeSuccessor(*ptr, SELF->nil);
  863.     
  864.     if (node == SELF->nil) {
  865.     *ptr = NULL;
  866.     
  867.     return NULL;
  868.     } else {
  869.     *ptr = node;
  870.     
  871.     return node->data;
  872.     }
  873. }
  874.  
  875.  
  876.  
  877. static void *previous(WMBag *self, WMBagIterator *ptr)
  878. {
  879.     W_Node *node;
  880.     
  881.     if (*ptr == NULL)
  882.     return NULL;
  883.     
  884.     node = treePredecessor(*ptr, SELF->nil);
  885.     
  886.  
  887.     if (node == SELF->nil) {
  888.     *ptr = NULL;
  889.     
  890.     return NULL;
  891.     } else {
  892.     *ptr = node;
  893.     
  894.     return node->data;
  895.     }
  896. }
  897.  
  898.  
  899.  
  900. static void *iteratorAtIndex(WMBag *self, int index, WMBagIterator *ptr)
  901. {
  902.     W_Node *node;
  903.     
  904.     node = treeSearch(SELF->root, SELF->nil, index);
  905.     
  906.     if (node == SELF->nil) {
  907.     *ptr = NULL;
  908.     return NULL;
  909.     } else {
  910.     *ptr = node;
  911.     return node->data;
  912.     }
  913. }
  914.  
  915.  
  916. static int indexForIterator(WMBag *bag, WMBagIterator ptr)
  917. {
  918.     return ((W_Node*)ptr)->index;
  919. }
  920.  
  921.